#include<assert.h>
#include<iostream>
#include<vector>
using namespace std;

template<class T>
class Heap
{
  public:
    Heap()
    {}
    ~Heap()
    {}
  public:
    void push(const T& val)
    {
      a.push_back(val);
      AdjustUp(a,a.size()-1);//从插入位置向上调整
    }
    void pop()
    {
      assert(!empty());
      swap(a[0],a[a.size()-1]); 
      a.pop_back();
      AdjustDown(a,0,a.size());
    }
    T& top()
    {
      assert(!empty());
      return a[0];
    }
    
    void AdjustDown(vector<T>& a,int parent,int n)
    {
      int child = parent*2+1; 
      while(child<n) //最坏情况:孩子调整到该路径的叶子节点
      {
        if(child +1 < n && a[child+1] >a[child])
          child+=1;
        if(a[child] > a[parent])
        {
          ::swap(a[child],a[parent]);
          parent = child;
          child = parent*2+1;
        }
        else 
        {
          break;
        }
      }
    }
    void AdjustUp(vector<T>& a,int child)
    {
      int parent = (child-1)/2;
      while(child > 0) //最坏情况:孩子调整到根节点结束
      {
         if(a[child] >a[parent])
         {
           swap(a[child],a[parent]);
           child = parent;
           parent =(child-1)/2;
         }
         else 
         {
           break;
         }
      }
    }
    bool empty()
    {
      return a.empty();
    }
    size_t size()
    {
      return a.size();
    }
  private:
    vector<T> a;
};
